package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 876. Middle of the Linked List
 *
 * Given the head of a singly linked list, return the middle node of the linked list.
 * If there are two middle nodes, return the second middle node.
 *
 * Example 1:
 *  Input: head = [1,2,3,4,5]
 *  Output: [3,4,5]
 *  Explanation: The middle node of the list is node 3.
 *
 * Example 2:
 *  Input: head = [1,2,3,4,5,6]
 *  Output: [4,5,6]
 *  Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
 *
 * Constraints:
 *  The number of nodes in the list is in the range [1, 100].
 *  1 <= Node.val <= 100
 */
public class Num_0876 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode middleNode(ListNode head);

        default void assertExpected(int[] head, int[] expected) {
            if (!assertEquals(middleNode(build(head)), build(expected))) {
                middleNode(build(head));
            }
        }
    }

    private static class MyAnotherSolution implements Solution {

        @Override
        public ListNode middleNode(ListNode head) { // 最优：快慢指针：时O(n) 空O(1)
            /*
             * 链表中点（快慢指针，进一步优化）
             * slow 每次走一步
             * fast 每次走两步
             * => 最后 slow 必然走到中间点（有两个中间点时取第二个）
             *
             *       [1,2,3,4,5,6,7]
             * 0:    [1,2,3,4,5,6,7]
             *        ↑
             * 1:    [1,2,3,4,5,6,7]
             *          ↑ ↑
             * 2:    [1,2,3,4,5,6,7]
             *            ↑   ↑
             * 3:    [1,2,3,4,5,6,7]
             *              ↑     ↑
             */
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next; // 走两步
                slow = slow.next; // 走一步
            }
            return slow;
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode middleNode(ListNode head) { // 其次：朴素快慢指针做法：时O(n) 空O(1)
            /*
             * 链表中点（快慢指针）
             *       [1,2,3,4,5,6,7]
             * 0:    [1,2,3,4,5,6,7] - move
             *        ↑
             * 1:    [1,2,3,4,5,6,7]
             *          ↑
             * 2:    [1,2,3,4,5,6,7] - move
             *          ↑ ↑
             * 3:    [1,2,3,4,5,6,7]
             *            ↑ ↑
             * 4:    [1,2,3,4,5,6,7] - move
             *            ↑   ↑
             * 5:    [1,2,3,4,5,6,7]
             *              ↑   ↑
             * 6:    [1,2,3,4,5,6,7] - move
             *              ↑     ↑
             */
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null && fast.next.next != null) { // 后面存在两个时移动
                fast = fast.next.next; // 走两步
                slow = slow.next; // 走一步
            }
            if (fast != null && fast.next != null) { // 后面仅存在一个时移动
                slow = slow.next; // 走一步
            }
            // 后面不存在时停止
            return slow;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyAnotherSolution();
        solution.assertExpected(new int[]{1,2,3,4,5}, new int[]{3,4,5});
        solution.assertExpected(new int[]{1,2,3,4,5,6}, new int[]{4,5,6});
    }
}
